package cn.my.mergeSort;

import java.util.Arrays;

public class MergeSort {
	public static void mergeSort(int[] a, int left, int right){
		if (left < right){
			int middle = (left+right) / 2;
			mergeSort(a, left, middle);
			mergeSort(a, middle+1, right);
			merge(a, left, middle, right);
		}
	}
	public static void merge(int[] a, int left, int middle, int right){
		int[] tmpArr = new int[right-left+1];
		int pos = 0;
		int i = left;
		int j = middle + 1;
		while (i<=middle && j<=right){
			if (a[i] <= a[j]){
				tmpArr[pos++] = a[i++];
			}else{
				tmpArr[pos++] = a[j++];
			}
		}
		while (i <= middle){
			tmpArr[pos++] = a[i++];
		}
		while (j <= right){
			tmpArr[pos++] = a[j++];
		}
		int start = 0;
		while (left <= right){
			a[left++] = tmpArr[start++];
		}
	}
	public static void main(String[] args) {
		int a[] = {3, 2, 4, 1, 5, 9, 6};
		mergeSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
	}
}
